1. Field of the Invention
This invention relates to the field of circuitry for decoding variable-length encoded data and in particular to circuitry for decoding variable-length encoded data having an unrestricted set of code words.
2. Background Art
Advances in the field of digital data processing have generated a demand for systems which can transfer, process, and store relatively large amounts of digital data. It is therefore often desirable that this digital data be compressed so that it may be more efficiently transmitted and so that it may be stored in a relatively small amount of memory.
An example of a digital data processing system requiring the transfer, processing, and storage of a relatively large volume of digital data is a video signal processing system. For example, a conventional video signal processing system may provide an image broken down into two hundred forty lines. Each line of the image may contain two hundred fifty six eight-bit independent pixel values. A video signal processing system of this type therefore requires 61,440 bytes for each image frame. Assuming an image display rate of thirty frames per second, this video processing system has a data rate of 1,843,200 bytes per second.
It is well known that the number of bytes per frame in a video signal processing system may be reduced by encoding in order to compress the video data. A prior art system of this type for encoding video data is described, for example, in U.S. Pat. No 4,125,861, entitled "Video Signal Encoding", which is incorporated by reference herein. In the video processing system described in this reference, the digital video data are first compressed using a differential pulse code modulation technique. The compressed data are then encoded using a variable-length code. In variable-length codes of this type the statistically more frequently occurring data values are assigned to the shorter code words and less frequently occurring data values are assigned to the longer code words. Thus fewer bits are required to encode the data. As used in this application, this type of encoding is referred to as statistical encoding.
One method known in the prior art for statistically encoding data in this manner is the use of an optimal variable-length code such as a Huffman code. To use a Huffman code, the data to be transmitted is put in order, from the most frequently occurring data values to the least frequently occurring ones. A Huffman code is then generated using, for example, the algorithm described at pages 77-85 of Information Theory add Coding by N. Abramson, McGraw Hill, 1963, which is incorporated by reference herein. Using this method, a code book which gives the correspondence between the data values and the code values is transmitted along with the encoded data. The transmitted code book permits the system which decodes the data to translate the code values into their corresponding data values. Because of the overhead of transmitting and storing the code book containing the encoded data this encoding technique is practical only when a relatively large amount of data is transmitted or stored.
It is well known in the art to use this statistical decoding method for codes of the form: EQU [11 . . . 10] [x(N) bits]
or EQU [00 . . . 01] [x(N) bits]
wherein N is the number of leading ones in the code prefix [11 . . . 10] or the number of leading zeros in the code prefix [00 . . . 01], and x(N) is a function of N specifying the number of bits forming the code value which follows the code prefix. In this method statistical decoding is performed by first scanning the input bits to be decoded and locating a code prefix. For example see U.S. Pat. No. 4,125,861. Then x(N) additional bits are fetched according to the length N of the located prefix. The fetched x(N) bits form a code value which serves as a unique index number. A unique index number indicates a data value which was previously encoded to represent one unique code in the code book. The code book may be specified by a small amount of memory containing the x(N) values.
Another known for statistically encoding data is processing the data according to a predetermined algorithm to obtain data having a statistical distribution of values which generally approximates a known distribution. The data are then encoded, using a code which has been adapted for the known distribution, transmitted, and then decoded using a fixed code book which is the inverse of the code book used to encode the data values.
U.S. Pat. No. 4,125,861 teaches a statistical system of this type wherein processing of data is performed to obtain a statistical distribution. Differential pulse code modulation processing is performed on input data by this system to produce data having a value distribution that has a peak at zero and falls off in a roughly exponential form on either side of the peak. These data are then statistically encoded using a preset code book stored in a read only memory. The data are then transmitted to a receiver which decodes the data using the inverse table, also stored in a read only memory.
A statistical system of the type taught in U.S. Pat. No. 4,125,861, has the advantage that it significantly compresses the input data and does not require transmission of a code book along with the compressed data. However, this type of statistical system has the disadvantage that the level of compression of the data obtained may not be as good as that which may be obtained if a more tailored statistical encoding scheme which is adapted to the data is used.
It would therefore be advantageous if a data encoding and decoding system could be provided that efficiently encoded data having a variety of statistical patterns but did not require restrictions on the permitted code book.